|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (vedoucí práce) ; Koutecký, Martin (oponent)
Cachování (také známo jako stránkování) je klasický problém modelující ob- sluhu dvouúrovňových pamět'ových systémů. Obecné cachování je varianta se stránkami různých velikostí a cen. V práci se zabýváme zpřesněním cha- rakterizace výpočetní složitosti obecného cachování v offline případě. Nedávno bylo dokázáno, že obecné cachování v offline případě je silně NP- těžké, ovšem v důkazu byly zapotřebí instance cachování se stránkami většími nežli polovina velikosti cache. Náš hlavní výsledek se vyrovnává s tímto pro- blémem: Dokazujeme, že obecné cachování je silně těžké již tehdy, když jsou velikosti stránek omezeny na {1, 2, 3}. Ve strukturální části práce pak před- stavujeme nový jednodušší důkaz úplné charakterizace work functions pomocí struktury layers v případě klasického cachování, důkaz je následně rozšířen na cachování s proměnlivou velikostí cache. Na základě těchto výsledků jsme zkonstruovali dva algoritmy pro speciální případy obecného cachování.
|
|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (vedoucí práce) ; Koutecký, Martin (oponent)
Cachování (také známo jako stránkování) je klasický problém modelující ob- sluhu dvouúrovňových pamět'ových systémů. Obecné cachování je varianta se stránkami různých velikostí a cen. V práci se zabýváme zpřesněním cha- rakterizace výpočetní složitosti obecného cachování v offline případě. Nedávno bylo dokázáno, že obecné cachování v offline případě je silně NP- těžké, ovšem v důkazu byly zapotřebí instance cachování se stránkami většími nežli polovina velikosti cache. Náš hlavní výsledek se vyrovnává s tímto pro- blémem: Dokazujeme, že obecné cachování je silně těžké již tehdy, když jsou velikosti stránek omezeny na {1, 2, 3}. Ve strukturální části práce pak před- stavujeme nový jednodušší důkaz úplné charakterizace work functions pomocí struktury layers v případě klasického cachování, důkaz je následně rozšířen na cachování s proměnlivou velikostí cache. Na základě těchto výsledků jsme zkonstruovali dva algoritmy pro speciální případy obecného cachování.
|
|
| |
host ::
RSS.